Route computation and optimization for vehicles, such as for example, water vehicles (e.g., ships, boats, hovercrafts, vessels, submarines, etc.), airborne vehicles (e.g., drones), or robots, becomes complex when the vehicle is supposed to use a route optimized towards a particular set of goals between a start location and a target location, and when, between the start and target location, one or more collision objects (or collision areas) exist. It is to be noted that water/airborne vehicles or robots are primarily not bound by any boundaries from predefined route options such as roads or rails. Rather, such vehicles are mostly free to use any direction on a surface or within a given height band. This increases the risk to run into collision objects. Such collision objects may be of a static type (e.g., landmass such as islands, coastal areas or areas with low water depth, mountains, lakes, etc.), or they may be of a dynamic type (e.g., areas with strong water/air currents or, more generally, difficult weather conditions that should be avoided, or areas to that exposure should be minimized).
Typically, such collision objects are represented by or approximated as polygonal representations modeling the shapes and locations of the respective collision objects on a map. This is sometimes called a polygonal environment. In addition, routes are typically computed as sequences of waypoints, which can be used to draw polygonal lines which may be smoothened by the computation of so-called splines or to draw sequences of great circle arcs to describe paths on a spherical shape.
When trying to compute a route under particular optimization constraints (e.g., land masses, etc.) and one or more target functions (e.g., as short as possible or as fast as possible), a mathematical optimization problem in a continuous environment has an infinite number of potential solutions which significantly impedes the selection of an appropriate route. The lack of knowledge about the number of intermediate steps, the possibly non-convex properties of the collision objects and, for example, the non-convex properties in the context of fuel consumption provide substantial challenges for the route computation. In cases of dynamic environments (non-static collision objects), a mathematically optimal solution is impractical and even with state-of the art computing power, not feasible.
Therefore, prior art solutions for solvable route computation in polygonal environment were suggested. These prior art solutions include cell decomposition, Voronoi diagrams, probability roadmaps, A star, and visibility graphs. However, because of discretization steps, some prior art solutions suffer from information loss inherent to the used algorithms which may prevent the computation of an optimal route. This leads to a situation where route computation cannot be performed in scenarios with quasi real-time computation requirement, and further consumes huge amounts of memory space. For example, in situations where a dynamic collision object needs to be avoided, it is advantageous to adjust the route of the ship very quickly because of the inertia of water vehicles. Further, it is desirable to perform such computations on mobile devices, such as smart phones or tablet computers with limited memory capacity and computing power. Hence, there is a need for providing a route computation systems and methods without information loss for highly accurate route computation which can be performed by low performance computing devices, with quasi-real-time response behavior.